375. 猜数字大小 II

没太理解原理，默写的题解

https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/

• 提交时间:2021-11-12 15:40:33
• 执行用时：12 ms, 在所有 Go 提交中击败了85.19%的用户
• 内存消耗：4.8 MB, 在所有 Go 提交中击败了53.70%的用户
• 通过测试用例：27 / 27

func getMoneyAmount(n int) (ans int) {
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    for leftPos := n - 1; leftPos > 0; leftPos-- {
        for rightPos := leftPos + 1; rightPos <= n; rightPos++ {
            ans = math.MaxInt32
            for k := leftPos; k < rightPos; k++ {
                ret := k + max(f[leftPos][k-1], f[k+1][rightPos])
                if ret < ans {
                    ans = ret
                }
            }
            f[leftPos][rightPos] = ans
        }
    }
    return
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}